package genetischeralgorithmus;

import java.util.*;
import java.awt.*;
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Dominik
 */
public class Recombination {

    public Recombination() {
    }

    public Entity[] crossover(Entity[][] crossPairs, int crossoverMethode, int coding, int placesCount) {

        if (coding == 1) {
            switch (crossoverMethode) {
                case 0: //One-Point-Crossover
                    return onePointX(crossPairs, placesCount);
                case 1: //Two-Point-Crossover
                    return twoPointX(crossPairs, placesCount);
                case 2: //Uniform-Crossover
                    return uniformPointX(crossPairs, placesCount);
            }
        } else {

            switch (crossoverMethode) {


                case 0:  //PMX (Partially-Mapped-Crossover
                    return pmx(crossPairs);
                case 1:  //OX (Order-Crossover)
                    return ox(crossPairs);
                case 2:   //AP (Alternating-Position-Crossover)
                    return ap(crossPairs);
                case 3:  //CX (Cycle-Crossover)
                    return cx(crossPairs);
                case 4:  //none
                    return none(crossPairs);

            }



        }
        return null;
    }

    public Entity[] pmx(Entity[][] crossPairs) {

        Entity[] newOffspring = new Entity[crossPairs.length];

        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {

            Random rand1 = new Random();
            int l = 0;
            int crossoverPoint1 = 0;
            int crossoverPoint2 = 0;


            int[] dad = crossPairs[breedingCount][0].getPath();
            int[] mum = crossPairs[breedingCount][1].getPath();

            int used[] = new int[dad.length];
            Arrays.fill(used, 0);
            int[] child = new int[dad.length];
            Arrays.fill(child, 0);


            Entity newEntity = new Entity(dad.length);

            crossoverPoint1 = rand1.nextInt(dad.length - 1);
            crossoverPoint2 = getRandomWithoutX(crossoverPoint1, dad.length - 1);

            if (crossoverPoint2 < crossoverPoint1) {
                l = crossoverPoint1;
                crossoverPoint1 = crossoverPoint2;
                crossoverPoint2 = l;
            }


            // übertrage einen zufälligen String in das Kind Chromosom
            for (int i = crossoverPoint1; i < crossoverPoint2; i++) {
                child[i] = dad[i];
            }

            // Für alle Werte die noch nicht übertragen wurden
            for (int i = crossoverPoint1; i < crossoverPoint2; i++) {
                if (getArrayposition(mum[i], child) == -1) {
                    step(mum[i], child, dad, mum, mum[i], crossoverPoint1, crossoverPoint2); //rekursive methode die mapping durchführt
                }
            }


            //auffüllen mit den restlichen Punkten aus MutterChromosom
            int childPos = 0;
            for (int k = 0; k < child.length; k++) {

                while (child[childPos] != 0 && childPos < child.length - 1) {
                    childPos++;
                }

                if (getArrayposition(mum[k], child) == -1) {
                    child[childPos++] = mum[k];
                }
            }

            newEntity.setPath(child);
            newOffspring[breedingCount] = newEntity;

        }


        return newOffspring;
    }

    public Entity[] ox(Entity[][] crossPairs) {

        Entity[] newOffspring = new Entity[crossPairs.length];

        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {

            Random rand1 = new Random();
            int l = 0;
            int crossoverPoint1 = 0;
            int crossoverPoint2 = 0;

            int[] mum = crossPairs[breedingCount][0].getPath();
            int[] dad = crossPairs[breedingCount][1].getPath();
            int[] child = new int[dad.length];
            Arrays.fill(child, 0);
            int place1 = 0;
            int place2 = 0;

            Entity newEntity = new Entity(dad.length);

            crossoverPoint1 = rand1.nextInt(dad.length - 1);
            crossoverPoint2 = getRandomWithoutX(crossoverPoint1, dad.length - 1);

            if (crossoverPoint2 < crossoverPoint1) {
                l = crossoverPoint1;
                crossoverPoint1 = crossoverPoint2;
                crossoverPoint2 = l;
            }

            for (int i = crossoverPoint1; i < crossoverPoint2; i++) {
                child[i] = dad[i]; //Teilpfada von 1. Elternteil uebernehmen
            }

            int fillPlacesCount = dad.length - (crossoverPoint2 - crossoverPoint1);

            int childPointer = crossoverPoint2;

            while (fillPlacesCount > 0) {


                if (crossoverPoint2 == dad.length) {
                    crossoverPoint2 = 0;   //Sprung zum Anfang wenn das Ende erreicht ist
                }
                if (childPointer == dad.length) {
                    childPointer = 0;   //Sprung zum Anfang wenn das Ende erreicht ist
                }

                if (getArrayposition(mum[crossoverPoint2], child) == -1) {
                    child[childPointer++] = mum[crossoverPoint2++];
                    fillPlacesCount--;
                } else {
                    crossoverPoint2++;
                }
            }

            newEntity.setPath(child);
            newOffspring[breedingCount] = newEntity;
        }

        return newOffspring;


    }

    public Entity[] ap(Entity[][] crossPairs) {

        Entity[] newOffspring = new Entity[crossPairs.length];

        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {

            Entity entity1 = crossPairs[breedingCount][0];
            Entity entity2 = crossPairs[breedingCount][1];
            int[] mum = crossPairs[breedingCount][0].getPath();
            int[] dad = crossPairs[breedingCount][1].getPath();
            int[] child = new int[dad.length];
            Arrays.fill(child, 0);


            int dadPos = 0;
            int mumPos = 0;
            for (int i = 0; i < child.length; i++) {

                while (getArrayposition(dad[dadPos], child) != -1) {  // sucht Element aus vaterChromosom, dass noch nicht in Child drin ist
                    dadPos++;
                }
                child[i++] = dad[dadPos++]; //fügt element von VaterChromosom ein

                if (i < child.length) { //checkt ob schon das ende erreicht wurde sonst gäbe es Nullpointer
                    while (getArrayposition(mum[mumPos], child) != -1) {  // sucht Element aus MutterChromosom, dass noch nicht in Child drin ist
                        mumPos++;
                    }
                    child[i] = mum[mumPos++]; //fügt element von MutterChromosom ein
                }
            }
            Entity newEntity = new Entity(entity1.getPath().length);
            newEntity.setPath(child);
            newOffspring[breedingCount] = newEntity;
        }

        return newOffspring;














    }

    public Entity[] cx(Entity[][] crossPairs) {

        Entity[] newOffspring = new Entity[crossPairs.length];


        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {


            int[] dad = crossPairs[breedingCount][0].getPath();
            int[] mum = crossPairs[breedingCount][1].getPath();
            int[] child = new int[dad.length];
            Entity newEntity = new Entity(dad.length);
            Random rand1 = new Random();
            int search = rand1.nextInt(dad.length - 1);
            int loopGuard = 0;
            boolean loop = false;



            while (dad[search] == mum[search] && !loop) {     //verhindert Problem,dass ersten beide Elemente gleich sind
                search = rand1.nextInt(dad.length - 1);
                loopGuard++;
                if (loopGuard > 2 * dad.length - 1) {  //falls Elemente gleich sind wird hier die Suche abgebrochen
                    loop = true;
                }
            }
            if (loop) {
                newEntity.setPath(dad);
                newOffspring[breedingCount] = newEntity;
            } else {  //recombination

                boolean[] visited = new boolean[dad.length];
                Arrays.fill(visited, false);

                int run = 0;
                int temp = search;
                int first = temp;
                visited[temp] = true;
                child[temp] = dad[temp];
                temp = getArrayposition(mum[temp], dad);

                while (temp != first) {
                    run++;
                    visited[temp] = true;
                    child[temp] = dad[temp];
                    temp = getArrayposition(mum[temp], dad);

                }

                for (int i = 0; i < child.length; i++) {
                    if (!visited[i]) {
                        child[i] = mum[i];
                    }
                }

                newEntity.setPath(child);
                newOffspring[breedingCount] = newEntity;
            }
        }
        return newOffspring;

    }

    public Entity[] none(Entity[][] crossPairs) {

        Entity[] newOffspring = new Entity[crossPairs.length];


        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {
            newOffspring[breedingCount] = new Entity(crossPairs[breedingCount][0].getPath().length);
            newOffspring[breedingCount].setPath(crossPairs[breedingCount][0].getPath());
        }
        return newOffspring;
    }

    public Entity[] onePointX(Entity[][] crossPairs, int placesCount) {

        Entity[] newOffspring = new Entity[crossPairs.length];


        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {


            int[] dadPath = crossPairs[breedingCount][0].getPath();
            int[] mumPath = crossPairs[breedingCount][1].getPath();
            int[] childPath = new int[dadPath.length];
            Entity newEntity = new Entity(dadPath.length);
            Random rand1 = new Random();
            int maxBinaryLength = Integer.toBinaryString(placesCount).length();
            int crossPoint = 0;

            String dad = "";
            String mum = "";

            //Eltern in binäre Form transformiernen
            for (int i = 0; i < dadPath.length; i++) { //alle Städte werden durchlaufen
                for (int j = Integer.toBinaryString(dadPath[i]).length(); j < maxBinaryLength; j++) { //Führende Nullen eintragen
                    dad = dad + "0";
                }
                dad = dad + Integer.toBinaryString(dadPath[i]);  // Binärstring eintragen

                //das selbe für das Mutter-Chromosom
                for (int j = Integer.toBinaryString(mumPath[i]).length(); j < maxBinaryLength; j++) {
                    mum = mum + "0";
                }
                mum = mum + Integer.toBinaryString(mumPath[i]);
            }

            int crosspoint = rand1.nextInt(dad.length());

            String child = dad.substring(0, crosspoint) + mum.substring(crosspoint, mum.length());

            // System.out.println("dad:" + Arrays.toString(dadPath));
            // System.out.println("mum:" + Arrays.toString(mumPath));


            childPath = repairbinaryChild(child, dadPath.length, maxBinaryLength);

            //  System.out.println("childPRep:" + Arrays.toString(childPath));

            newEntity.setPath(childPath);
            newOffspring[breedingCount] = newEntity;

        }
        return newOffspring;

    }

    public Entity[] twoPointX(Entity[][] crossPairs, int placesCount) {
        Entity[] newOffspring = new Entity[crossPairs.length];


        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {


            int[] dadPath = crossPairs[breedingCount][0].getPath();
            int[] mumPath = crossPairs[breedingCount][1].getPath();
            int[] childPath = new int[dadPath.length];
            Entity newEntity = new Entity(dadPath.length);
            Random rand1 = new Random();
            int maxBinaryLength = Integer.toBinaryString(placesCount).length();



            String dad = "";
            String mum = "";

            //Eltern in binäre Form transformiernen
            for (int i = 0; i < dadPath.length; i++) { //alle Städte werden durchlaufen
                for (int j = Integer.toBinaryString(dadPath[i]).length(); j < maxBinaryLength; j++) { //Führende Nullen eintragen
                    dad = dad + "0";
                }
                dad = dad + Integer.toBinaryString(dadPath[i]);  // Binärstring eintragen

                //das selbe für das Mutter-Chromosom
                for (int j = Integer.toBinaryString(mumPath[i]).length(); j < maxBinaryLength; j++) {
                    mum = mum + "0";
                }
                mum = mum + Integer.toBinaryString(mumPath[i]);
            }

            int crosspoint1 = rand1.nextInt(dad.length());
            int crosspoint2 = getRandomWithoutX(crosspoint1, dad.length() - 1);
            int l = 0;
            if (crosspoint2 < crosspoint1) {
                l = crosspoint1;
                crosspoint1 = crosspoint2;
                crosspoint2 = l;
            }

            String child = dad.substring(0, crosspoint1) + mum.substring(crosspoint1, crosspoint2) + dad.substring(crosspoint2, dad.length());

            //System.out.println("dad:" + Arrays.toString(dadPath));
            //System.out.println("mum:" + Arrays.toString(mumPath));

            childPath = repairbinaryChild(child, dadPath.length, maxBinaryLength);

            newEntity.setPath(childPath);
            newOffspring[breedingCount] = newEntity;

        }
        return newOffspring;
    }

    public Entity[] uniformPointX(Entity[][] crossPairs, int placesCount) {
        Entity[] newOffspring = new Entity[crossPairs.length];


        for (int breedingCount = 0; breedingCount < crossPairs.length; breedingCount++) {


            int[] dadPath = crossPairs[breedingCount][0].getPath();
            int[] mumPath = crossPairs[breedingCount][1].getPath();
            int[] childPath = new int[dadPath.length];
            Entity newEntity = new Entity(dadPath.length);
            Random rand1 = new Random();
            int maxBinaryLength = Integer.toBinaryString(placesCount).length();


            String dad = "";
            String mum = "";

            //Eltern in binäre Form transformiernen
            for (int i = 0; i < dadPath.length; i++) { //alle Städte werden durchlaufen
                for (int j = Integer.toBinaryString(dadPath[i]).length(); j < maxBinaryLength; j++) { //Führende Nullen eintragen
                    dad = dad + "0";
                }
                dad = dad + Integer.toBinaryString(dadPath[i]);  // Binärstring eintragen

                //das selbe für das Mutter-Chromosom
                for (int j = Integer.toBinaryString(mumPath[i]).length(); j < maxBinaryLength; j++) {
                    mum = mum + "0";
                }
                mum = mum + Integer.toBinaryString(mumPath[i]);
            }

            //hier findet der Uniform-Crossover statt. mit einer 50/50 Wahrscheinlichkeit wird ein element des
            //ersten oder des zweioten elternteils in das Kind kopiert.

            String child = "";
            for (int k = 0; k < dad.length(); k++) {
                if (rand1.nextBoolean()) {
                    child = child + dad.charAt(k);
                } else {
                    child = child + mum.charAt(k);
                }
            }



            // System.out.println("dad:" + Arrays.toString(dadPath));
            // System.out.println("mum:" + Arrays.toString(mumPath));


            childPath = repairbinaryChild(child, dadPath.length, maxBinaryLength);

            //  System.out.println("childPRep:" + Arrays.toString(childPath));

            newEntity.setPath(childPath);
            newOffspring[breedingCount] = newEntity;

        }
        return newOffspring;
    }

    public int getRandomWithoutX(int x, int max) {
        boolean found = false;
        int random = 0;
        while (!found) {
            random = new Random().nextInt(max);
            if (random != x) {
                found = true;
            }
        }
        return random;
    }

    public int getArrayposition(int item, int[] array) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == item) {
                return i;
            }
        }
        return -1;
    }

    public void step(int initvalue, int[] child, int[] dad, int[] mum, int value, int cross1, int cross2) {

        int valuePosition = getArrayposition(value, mum);
        int valueDad = dad[valuePosition];
        int positionMumNew = getArrayposition(valueDad, mum);
        if (positionMumNew >= cross1 && positionMumNew < cross2) {
            step(initvalue, child, dad, mum, valueDad, cross1, cross2);
        } else {
            child[positionMumNew] = initvalue;

        }
    }

    public int[] repairbinaryChild(String child, int pathLength, int binaryLength) {

        int[] childPath = new int[pathLength];

        int k = 0; //Laufvariable für den Child-String
        for (int i = 0; i < pathLength; i++) { //jede Pfadposition durchlaufen

            String subString = child.substring(k, k + binaryLength);
            childPath[i] = Integer.parseInt(subString, 2);  //transformiert binäre Kodierung in Pfadcodierung um die Reparatur zu ermöglichen
            k += binaryLength;
        }

        LinkedList<Integer> illegalPosList = new <Integer>LinkedList();
        for (int i = 0; i < childPath.length; i++) {
            if ((getArrayposition(childPath[i], Arrays.copyOfRange(childPath, 0, i)) != -1) || (childPath[i] > pathLength) || childPath[i] == 0) {
                childPath[i] = 0;  //setzt doppelte oder ungültige Orte auf 0
                illegalPosList.add(i);

            }
        }

        // System.out.println("set:"+ Arrays.toString(childPath));
        for (int j = 1; j < childPath.length + 1; j++) {
            boolean exists = false;
            for (int i = 0; i < childPath.length; i++) {
                if (childPath[i] == j) {
                    exists = true;
                }
            }
            if (!exists) {

                childPath[illegalPosList.pop()] = j;
            }
        }


        return childPath;
    }
}
